# 华为面试题q2，给定一个待处理字符串以及若干子串，要求在待处理字符串中找到这若干子串
# 投影可以把一个二维问题映射为一维问题
def findStr(s,ss,res):
    if s=="":
        return
    dp=[]
    for i in range(len(ss)):
        dp.append([0]*len(s))
    for i in range(len(s)):
        if s[i]==ss[0]:
            dp[0][i]=1
    for i in range(len(ss)):
        if ss[i]==s[0]:
            dp[i][0]=1
    
    for i in range(1,len(ss)):
        for j in range(1,len(s)):
            if ss[i]==s[j]:
                dp[i][j]=dp[i-1][j-1]+1
    # print(dp[-1])
    for i in range(len(dp[-1])):
        if dp[-1][i]==len(ss):
            for j in range(i-len(ss)+1,i+1):
                res[j]=1
            break
    # print(res)

def main():
    s="abcabcdefghiab"
    ss=["ac","fgh","hi"]
    res=[0]*len(s)
    for item in ss:
        findStr(s,item,res)
    print(res)

main()